#ifndef __DOUBLELINKLIST_HPP_
#define __DOUBLELINKLIST_HPP_

#include <stddef.h>
template <typename T>
class DoubleLinkList
{
public:
    DoubleLinkList();
    ~DoubleLinkList();
    void InsertTail(const T &element);
    void RemoveByIndex(size_t index);
    T &FindByIndex(size_t index);
    size_t Size(){return size;}

    template <typename U>
    friend std::ostream &operator<<(std::ostream &os, const DoubleLinkList<U> &list);

private:
    struct Node
    {
        Node(const T &element)
        {
            data = element;
            next = prev = nullptr;
        }
        T data;
        Node *next;
        Node *prev;
    };
    Node *head;
    Node *tail;
    size_t size;
};

template <typename T>
std::ostream &operator<<(std::ostream &os, const DoubleLinkList<T> &list)
{
    // 告诉编译器后面跟的是一个数据类型
    typename DoubleLinkList<T>::Node *travelPoint = list.head->next;
    while (travelPoint != nullptr)
    {
        std::cout << travelPoint->data << " ";
        travelPoint = travelPoint->next;
    }
    std::cout << std::endl;
    return os;
}

template <typename T>
DoubleLinkList<T>::DoubleLinkList() : size(0)
{
    head = tail = new Node(T()); // T() 匿名对象 T()会调用T的默认构造函数
}

template <typename T>
DoubleLinkList<T>::~DoubleLinkList()
{
    while (head != nullptr)
    {
        Node *nextNode = head->next;
        delete head;
        head = nextNode;
    }
    head = tail = nullptr;
}

template <typename T>
void DoubleLinkList<T>::InsertTail(const T &element)
{
    Node *newNode = new Node(element);
    tail->next = newNode;
    newNode->prev = tail;
    tail = newNode;
    size++;
}

template <typename T>
void DoubleLinkList<T>::RemoveByIndex(size_t index)
{
    if (index >= size)
    {
        return;
    }
    Node *TravelPoint = head;
    for (size_t i = 0; i < index; i++)
    {
        TravelPoint = TravelPoint->next;
    }
    Node *freeNode = TravelPoint->next;

    TravelPoint->next = freeNode->next;
    if (freeNode->next != nullptr)
        freeNode->next->prev = TravelPoint;
    else     // 删除的最后一个节点
        tail = TravelPoint; 
    delete freeNode;
    size--;
}

template <typename T>
T &DoubleLinkList<T>::FindByIndex(size_t index)
{
    typename DoubleLinkList<T>::Node *TravelPoint = head->next;
    for (size_t i = 0; i < index; i++)
    {
        TravelPoint = TravelPoint->next;
    }
    return TravelPoint->data;
}

#endif